package com.it.zhangjun.arithmetic.栈;

import java.util.Stack;

/**
 * @author zhangj
 * @description 判断字符串括号是否合法
 * @date 2021-03-18 14:10
 */
public class LT_判断字符串括号是否合法 {
    public static void main(String[] args) {
        System.out.println(isValid2("(())"));
    }

    private static boolean isValid1(String s) {
        //当字符串是空的时候，可以快速返回true
        if (s == null || s.length() == 0) {
            return true;
        }

        //字符串长度是奇数，肯定是不合法
        if (s.length() % 2 == 1) {
            return false;
        }

        //"("入栈 ")"出栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            //取出字符
            char c = s.charAt(i);
            if (c == '(') {
                //入栈
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    return false;
                }
                //弹栈
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    private static boolean isValid2(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        //奇数个字符，肯定为false
        if (s.length() % 2 == 1) {
            return false;
        }

        int leftBraceNumber = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftBraceNumber++;
            } else if (c == ')') {
                if (leftBraceNumber <= 0) {
                    return false;
                }
                leftBraceNumber--;
            }
        }
        return leftBraceNumber == 0;
    }
}